package org.hot100_6.leetcode146;

import java.util.HashMap;

public class Solution {
        public class LRUCache{

            class Node{
                int key;
                int val;
                Node next;
                Node pre;

               public Node (int val){
                    this.val = val;
                }

                public Node(int key,int val){
                   this.val = val;
                   this.key = key;
                }
            }

            HashMap<Integer,Node> hashMap = new HashMap<>();

            int size;

            Node dummy = new Node(-1);

            public LRUCache(int capacity) {
                this.size = capacity;
                dummy.next = dummy;
                dummy.pre = dummy;
            }

            public int get(int key) {
                if (hashMap.containsKey(key)){
                    Node node = hashMap.get(key);
                    //放到前面
                    deleteNode(node);
                    addHead(node);
                    return node.val;
                }else {
                    return -1;
                }
            }


            public void deleteNode(Node node){
                // 删除节点
                Node pre = node.pre;
                Node next = node.next;
                pre.next = next;
                next.pre = pre;
            }

            public void addHead(Node node){

                // 添加节点
                Node dummyNext = dummy.next;
                node.next = dummyNext;
                dummyNext.pre = node;
                node.pre = dummy;
                dummy.next = node;
            }

            public void put(int key, int value) {
                if (hashMap.containsKey(key)){
                    Node node = hashMap.get(key);
                    node.val = value;
                    hashMap.put(key,node);
                    deleteNode(node);
                    addHead(node);
                }else {
                    Node newNode = new Node(key,value);
                    hashMap.put(key,newNode);
                    addHead(newNode);
                    if (hashMap.size()>size){
                        Node deleteNode = dummy.pre;
                        hashMap.remove(deleteNode.key);
                        deleteNode(deleteNode);
                    }
                }
            }
        }
}
